package 程序员面试金典;

import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;

public class SortedStack {
    Deque<Integer> deque;
    Deque<Integer> temp;
    public SortedStack() {
        deque = new LinkedList<Integer>();
        temp = new LinkedList<Integer>();
    }

    public void push(int val) {
        while (!deque.isEmpty() && deque.peek()<val){
            temp.push(deque.pop());
        }
        deque.push(val);
        while (!temp.isEmpty()){
            deque.push(temp.pop());
        }
    }

    public void pop() {
        if (deque.isEmpty())
            return;
        deque.pop();
    }

    public int peek() {
        if (deque.isEmpty())
            return -1;
        return deque.peek();
    }

    public boolean isEmpty() {
         return deque.isEmpty();
    }
}
